//
// Created by lights on 24-7-1.
//

#include <iostream>
#include <vector>
#include <cmath>

int length(int i) {
    int k = 1;
    i = i - i / 2;
    while (i > 0) {
        k++;
        i = i - i / 2;
    }
    return k;
}

void compress(int n, const std::vector<int>& p, std::vector<int>& s, std::vector<int>& l, std::vector<int>& b) {
    int Lmax = 256;
    int header = 11;
    s[0] = 0;

    for (int i = 1; i <= n; i++) {
        b[i] = length(p[i]);
        int bmax = b[i];
        s[i] = s[i - 1] + bmax;
        l[i] = 1;

        for (int j = 2; j <= i && j <= Lmax; j++) {
            if (bmax < b[i - j + 1]) {
                bmax = b[i - j + 1];
            }
            if (s[i] > s[i - j] + j * bmax) {
                s[i] = s[i - j] + j * bmax;
                l[i] = j;
            }
        }
    }

    s[n] += header;
}


int main() {
    int n = 10;  // 假设有10个像素
    std::vector<int> p = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};  // 像素值数组
    std::vector<int> s(n + 1, 0);  // 最优压缩大小数组
    std::vector<int> l(n + 1, 0);  // 每个块的长度
    std::vector<int> b(n + 1, 0);  // 每个块的压缩位数

    compress(n, p, s, l, b);

    // 输出结果
    std::cout << "最优压缩大小: " << s[n] << std::endl;
    std::cout << "每个块的长度: ";
    for (int i = 1; i <= n; i++) {
        std::cout << l[i] << " ";
    }
    std::cout << std::endl;
    std::cout << "每个块的压缩位数: ";
    for (int i = 1; i <= n; i++) {
        std::cout << b[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}